/* Complex 16 bit Radix 4 FFT and Inverse FFT for Cortex-M3    version 1.0
--------------------------------------------------------------------------
(c) 2008 Ivan Mellen   
--------------------------------------------------------------------------
Free Personal, Non-Commercial Use License. 
The Software is licensed to you for your personal, NON-COMMERCIAL USE.
If you have questions about this license or would like a different license
please email : imellen(at)embeddedsignals(dot)com

 - Radix 4 FFT - supported sizes: N=4,16,64,256,1024,4096
 - N>4096 possible with custom coefficients  
 - 16 bit complex arithmetic, 1Q15 coefficients
 - input data remains unmodified
 - decimation-in-time with auto scale after each stage - no overflow 
 - GCC version (Code Sourcery G++ Lite 2007q3-53), requires C preprocessor
 - hand optimized THUMB2 assembly for Cortex-M3 (e.g. STM32)
 - code optimized with 64 bit flash prefetch and branch speculation in mind
 - single function for multiple FFT sizes
 - functions are both "C" and assembly callable

Modifications in version 2.0:
 - Constant size FFT (faster execution, but N is constant)
 - purely real input (almost 2x faster)
 - radix 2 stage (for N= 8, 32, 128, 512, 2048, 8192...)
 - RAM based coefficients with size optimized generator (for high flash latency)
 - speed optimized windowing function(Bartlett,Blackman, Hamming, Hanning, Kaiser)


STM32 FFT benchmarks in CPU cycles based on real hardware measurements:

 N - FFT size
 L - Flash latency
 F,R - coefficients in Flash or RAM

    N    L=0 F/R    L=1 F   L=1 r*   L=2 F*     L=2 r*   ARM7TDMI  ARM9E  dsPIC
   64     3575      3797     3636     4588      4007       -        2701   3739
  256    19425     20685    19743    25144     21685  38461-43920  13740  19055
 1024    98541    105113   100074   128070    109634       -       68534    N/A

Notes:ARM9E - DSP enhanced arm9 core, based on STR910 @96 MHz, RAM coefficients
      dsPIC - dsPIC30x / dsPIC33x - results based on Microchip's DSP library 
      ARM7TDMI - 3rd party, web based benchmark results
      *STM32 results for latency L=2 or  - source compiled with LATENCY2 defined

IFFT benchmarks (calculated and verified by measurement):
  add 6+N/4 to FFT benchmark {22,70,262} for N={64,256,1024}

Code size:
FFT only:  480 bytes
FFT+IFFT:  682 bytes

Coefficient size (Flash or RAM):
   N: 16  64  256  1024  4096
size: 48 240 1008  4080 16368  bytes

------------------------------------------------------------------------------
Usage example: add this file to your project. In C code:

//declare functions
void fftR4(short *y, short *x, int N);
void ifftR4(short *y, short *x, int N);

// prepare test input data
short x[512]; // input data 16 bit, 4 byte aligned  x0r,x0i,x1r,x1i,....
short y[512]; // output data 16 bit,4 byte aligned  y0r,y0i,y1r,y1i,....
short z[512]; // same format...

for (i=0;i<512;i++) x[i]=0;
for (i=0;i<512;i=i+8)
  { x[i+0]=16384; x[i+2]=16384;	x[i+4]=-16384;  x[i+6]=-16384;}
// x = [ 16384,16384,-16384,-16384,16384,...]  1/4 Fsampling

//call functions
fftR4(y, x, 256);   // y is in frequency domain y[128]=
ifftR4(z, y, 256);  // z should be x/N + noise introduced by 16 bit truncating 
 

// expected results:
//y[128]is 8191; y[129] is -8190   y[384]is 8191; y[385]is 8191 rest 0 + noise
//z[2n] is 64 64 -64 -64 ..  z[2n+1] is 0    all +- 1 (noise)
------------------------------------------------------------------------------
*/

 // This file contains two functions :

 // void fftR4(short *y, short *x, int N);   // radix 4 FFT
 // void ifftR4(short *y, short *x, int N);  // radix 4 inverse FFT
         
        .syntax unified
	.thumb
        .global fftR4  
        .global ifftR4   

//#define LATENCY2  //comment this line if flash latency lower than 2

#define y      R0    // short *y -output complex array  
#define x      R1    // short *x -input complex array  
#define N      R2    // int N - number of samples 4,16,64,256,1024,4096

#define c      R0    // short *c - coefficient array
#define Bl     R2    // the number of blocks
#define R      R3    // the number of samples in each block
#define x0r    R4
#define x0i    R5
#define x1r    R6
#define x1i    R7
#define x2r    R8
#define x2i    R9
#define x3r    R10
#define x3i    R11
#define y3r    x3i
#define y3i    x3r
#define tmp0   R12   // temporary0
#define tmp1   R14   // temporary1

       // complex load, x=[a], a+=offset in register data from RAM (0 wait states)

      .macro    LOADC   dr,di, a, offset   //5 cycles
                ldrsh   \di, [\a, #2]
		ldrsh   \dr, [\a]	  //ldrsh   $x._r, [$a], $offset
		adds 	\a, \offset
      .endm

        // cofficient complex load, c=[a], a=a+ 4  ;Wk from FLASH (1-4 wait states)
      .macro   LOADCF   xr,xi, a                //4 cycles
		ldr   \xr, [\a], #4		//read 2 shorts as 32 bits
		asr   \xi, \xr,#16		//im extract
		sxth  \xr,\xr			//re extract
      .endm
   
        // coefficient complex load, c=[a], a=a+ 4   ; Wk  from RAM (0 wait states)
//    .macro  LOADCF  xr,xi, a   //4 (or 3?) cycles
//          ldrsh   \xi, [$a, #2]
//	    ldrsh   \xr, [$a],#4  //ldrsh not pipelined in STM32, macro not used
//    .endm
  
  // complex load, xc=[a], a=a-register offset
       .macro   LOADCMi   xr,xi, a, offset   //5 cycles
        ldrsh   \xi, [\a, #2]
        ldrsh   \xr, [\a]
	subs 	\a, \offset	   //ldrsh   \xr, [$a], \offset
       .endm

        // complex store, [a]=x,c a=a+ immediate offset 
      .macro   STRC   xr,xi, a, offset   //2 cycles
        strh    \xi, [\a, #2]
        strh    \xr, [\a], \offset
      .endm        

        // complex store, [a]=x, a+=offset in register
      .macro  STRCR   xr,xi, a, offset   //3 cycles
        strh    \xi, [\a, #2]
        strh    \xr, [\a]
	adds 	\a, \offset
      .endm 


        // Multiply Complex Conjugate a=(xr+i*xi)*(cr-i*ci)
        //  x = xr + i*xi 
        //  c = cr + i*ci  ;6 cycles
    .macro   MULCC ar,ai, xr,xi,cr,ci
    	mul  tmp0, \xi, \cr            // tmp0=xi*cr
	mul  tmp1, \xi, \ci            // tmp1=xi*ci
        mls   \ai, \xr, \ci,tmp0       // ai=tmp0-xr*ci  =  xi*cr - xr*ci
	mla   \ar, \xr, \cr,tmp1       // ar=tmp1+xr*cr  =  xr*cr + xi*ci
     .endm

        
        // complex Fast Fourier Transform - Four point; scale with shift s
       .macro    BFFT4  s
       
        add     x2r, x2r, x3r   // (x2,x3) = (x2+x3, x2-x3)
        add     x2i, x2i, x3i
        sub     x3r, x2r, x3r, lsl#1
        sub     x3i, x2i, x3i, lsl#1
       
        mov     x0r, x0r, asr#2   // (x0,x1) = (x0+(x1>>s), x0-(x1>>s))/4
        mov     x0i, x0i, asr#2
        add     x0r, x0r, x1r, asr#(2+\s)
        add     x0i, x0i, x1i, asr#(2+\s)
        sub     x1r, x0r, x1r, asr#(1+\s)
        sub     x1i, x0i, x1i, asr#(1+\s)
       
        add     x0r, x0r, x2r, asr#(2+\s)   // (x0,x2) = (x0+(x2>>s)/4, x0-(x2>>s)/4)
        add     x0i, x0i, x2i, asr#(2+\s) 
        sub     x2r, x0r, x2r, asr#(1+\s)
        sub     x2i, x0i, x2i, asr#(1+\s)
        
        add     x1r, x1r, x3i, asr#(2+\s)  // (x1,y3)=(x1-i*(x3>>s)/4, x1+i*(x3>>s)/4)
        sub     x1i, x1i, x3r, asr#(2+\s)
        sub     y3r, x1r, x3i, asr#(1+\s)
        add     y3i, x1i, x3r, asr#(1+\s)
       .endm
        

 
//----------------------------------------------------------------------------
// inverse FFT 
// void ifftR4(short *y, short *x, int N) 
// custom first stage reorders input data: x(n)=x(N-n) n=0:N-1  x(N)=x(0)
// extra cost to fft: 6+N/4 cycles
        .thumb_func
        .align 3  //speed optimization in STM32
        nop.n //alignment optimization

ifftR4: stmfd   sp!, {r4-r11, lr}
        mov     tmp0, #0            // bit reversed counter
        movs 	tmp1,N     //; first tmp1=N  
	.word 0xF3A2FA92  //RBIT R3,R2	//RBIT R,N
	lsl     R,#3

	adds    tmp1,  x, tmp1, lsl#2 // tmp1=&x[tmp1==N] 
        ldrsh   x0i, [x, #2]   // replaces  C_LDRmi x[N] by _LDRmi x[0] 
        ldrsh   x0r, [x]
        subs  tmp1,N     //tmp1 still needs to be decremented for 2nd C_LDRmi
        b L2  // continue with second load

ifirstStage:
        // first stage load and bit reverse
        adds    tmp1,  x, tmp1, lsl#2 // tmp1=&x[tmp1] 
        LOADCMi   x0r,x0i, tmp1, N
L2:     LOADCMi   x2r,x2i, tmp1, N
        LOADCMi   x1r,x1i, tmp1, N
        LOADCMi   x3r,x3i, tmp1, N
         BFFT4  0
        STRC   x0r,x0i, y, #4
        STRC   x1r,x1i, y, #4
        STRC   x2r,x2i, y, #4
        STRC   y3r,y3i, y, #4
   		
       adds tmp0,R
       .word 0xFEACFA9C // rbit r14,r12//rbit tmp1,tmp0
       sub tmp1,N,tmp1  //tmp1=N-tmp1    
       bne     ifirstStage // loop if count non zero  
       b firstStageFinished
        // rest same as normal fft
 
 //----------------------------------------------------------------------------
 // void fftR4(short *y, short *x, int N)
      .thumb_func
fftR4:   stmfd   sp!, {r4-r11, lr}
        mov     tmp0, #0            // bit reversed counter
        mov 	tmp1, #0
        .word 0xF3A2FA92  //rbit R3,R2	//RBIT R,N
	lsl     R,#3

firstStage:
        // first stage load and bit reverse
        adds    tmp1,  x, tmp1, lsl#2 // tmp1=&x[tmp1] and clear carry
        LOADC   x0r, x0i, tmp1, N
        LOADC   x2r,x2i, tmp1, N
        LOADC   x1r,x1i, tmp1, N
        LOADC   x3r,x3i, tmp1, N
        BFFT4  0
        STRC   x0r,x0i, y, #4
        STRC   x1r,x1i, y, #4
        STRC   x2r,x2i, y, #4
        STRC   y3r,y3i, y, #4
   		
       adds tmp0,R
       .word 0xFEACFA9C // rbit r14,r12//rbit tmp1,tmp0
       bne     firstStage // loop if count non zero
   
firstStageFinished:        // finished the first stage
        sub     x, y, N, lsl #2   // x = working buffer
        mov     R, #16
        lsrs Bl,N,4  
        it eq
        ldmeq sp!, {r4-r11, pc}	 // for N==4 return from function
        adr     c, coef_table	//change if table in RAM 
                
nextStage:
        // Bl = the number of blocks
        // R = the number of samples in each block
 
#ifdef LATENCY2       // narrow/wide versions to optimize flash pre-fetch
        stm   sp!, {x, Bl}   
        add     tmp0, R, R, lsl#1
        add.n     x, x, tmp0    
#else
        stmfd   sp!, {x, Bl}  
        add     tmp0, R, R, lsl#1
        add.w     x, x, tmp0   
#endif
        sub     Bl, Bl, #1<<16
nextBlock:
        add     Bl, Bl, R, lsl#(16-2)

nextButterfly:
        // Bl=((number butterflies left-1)<<16) + (number of blocks left)
        LOADCMi   x0r,x0i, x, R
        LOADCF   x3r,x3i, c
        MULCC x3r,x3i, x0r,x0i, x3r,x3i
        LOADCMi   x0r,x0i, x, R
        LOADCF   x2r,x2i, c
        MULCC x2r,x2i, x0r,x0i, x2r,x2i
        LOADCMi   x0r,x0i, x, R
        LOADCF   x1r,x1i, c
        MULCC x1r,x1i, x0r,x0i, x1r,x1i
        LOADC   x0r,x0i, x, #0
        BFFT4  15              // coefficients are 1Q15
        STRCR  x0r,x0i, x, R
        STRCR  x1r,x1i, x, R
        STRCR  x2r,x2i, x, R
        STRC   y3r,y3i, x, #4
        subs    Bl, Bl, #1<<16
        bge     nextButterfly
        add     tmp0, R, R, lsl#1
        add     x, x, tmp0
        sub     Bl, Bl, #1
        movs    tmp1, Bl, lsl#16
        it ne
        subne   c, c, tmp0
        bne     nextBlock
        
        pop {r1-r2}   //LDM sp!, {x, Bl}
        mov     R, R, lsl#2     // block size *=4
        lsrs Bl,Bl,2            //# of blocks /=4
        bne     nextStage
        ldmfd   sp!, {r4-r11, pc}	 //return
      
        .align 2 //32 bit access acceleration

// Note: unused portion of coef_table can be commented to reduce size
coef_table:
        // FFT twiddle table of triplets E(3t), E(t), E(2t)
        // Where E(t)=cos(t)+i*sin(t) at 1Q15
        // N=16 t=2*PI*k/N for k=0,1,2,..,N/4-1
        .hword 0x7fff,0x0000, 0x7fff,0x0000, 0x7fff,0x0000
        .hword 0x30fc,0x7642, 0x7642,0x30fc, 0x5a82,0x5a82
        .hword 0xa57e,0x5a82, 0x5a82,0x5a82, 0x0000,0x7fff
        .hword 0x89be,0xcf04, 0x30fc,0x7642, 0xa57e,0x5a82
        // N=64 t=2*PI*k/N for k=0,1,2,..,N/4-1
        .hword 0x7fff,0x0000, 0x7fff,0x0000, 0x7fff,0x0000
        .hword 0x7a7d,0x2528, 0x7f62,0x0c8c, 0x7d8a,0x18f9
        .hword 0x6a6e,0x471d, 0x7d8a,0x18f9, 0x7642,0x30fc
        .hword 0x5134,0x62f2, 0x7a7d,0x2528, 0x6a6e,0x471d
        .hword 0x30fc,0x7642, 0x7642,0x30fc, 0x5a82,0x5a82
        .hword 0x0c8c,0x7f62, 0x70e3,0x3c57, 0x471d,0x6a6e
        .hword 0xe707,0x7d8a, 0x6a6e,0x471d, 0x30fc,0x7642
        .hword 0xc3a9,0x70e3, 0x62f2,0x5134, 0x18f9,0x7d8a
        .hword 0xa57e,0x5a82, 0x5a82,0x5a82, 0x0000,0x7fff
        .hword 0x8f1d,0x3c57, 0x5134,0x62f2, 0xe707,0x7d8a
        .hword 0x8276,0x18f9, 0x471d,0x6a6e, 0xcf04,0x7642
        .hword 0x809e,0xf374, 0x3c57,0x70e3, 0xb8e3,0x6a6e
        .hword 0x89be,0xcf04, 0x30fc,0x7642, 0xa57e,0x5a82
        .hword 0x9d0e,0xaecc, 0x2528,0x7a7d, 0x9592,0x471d
        .hword 0xb8e3,0x9592, 0x18f9,0x7d8a, 0x89be,0x30fc
        .hword 0xdad8,0x8583, 0x0c8c,0x7f62, 0x8276,0x18f9
        // N=256 t=2*PI*k/N for k=0,1,2,..,N/4-1
        .hword 0x7fff,0x0000, 0x7fff,0x0000, 0x7fff,0x0000
        .hword 0x7fa7,0x096b, 0x7ff6,0x0324, 0x7fd9,0x0648
        .hword 0x7e9d,0x12c8, 0x7fd9,0x0648, 0x7f62,0x0c8c
        .hword 0x7ce4,0x1c0c, 0x7fa7,0x096b, 0x7e9d,0x12c8
        .hword 0x7a7d,0x2528, 0x7f62,0x0c8c, 0x7d8a,0x18f9
        .hword 0x776c,0x2e11, 0x7f0a,0x0fab, 0x7c2a,0x1f1a
        .hword 0x73b6,0x36ba, 0x7e9d,0x12c8, 0x7a7d,0x2528
        .hword 0x6f5f,0x3f17, 0x7e1e,0x15e2, 0x7885,0x2b1f
        .hword 0x6a6e,0x471d, 0x7d8a,0x18f9, 0x7642,0x30fc
        .hword 0x64e9,0x4ec0, 0x7ce4,0x1c0c, 0x73b6,0x36ba
        .hword 0x5ed7,0x55f6, 0x7c2a,0x1f1a, 0x70e3,0x3c57
        .hword 0x5843,0x5cb4, 0x7b5d,0x2224, 0x6dca,0x41ce
        .hword 0x5134,0x62f2, 0x7a7d,0x2528, 0x6a6e,0x471d
        .hword 0x49b4,0x68a7, 0x798a,0x2827, 0x66d0,0x4c40
        .hword 0x41ce,0x6dca, 0x7885,0x2b1f, 0x62f2,0x5134
        .hword 0x398d,0x7255, 0x776c,0x2e11, 0x5ed7,0x55f6
        .hword 0x30fc,0x7642, 0x7642,0x30fc, 0x5a82,0x5a82
        .hword 0x2827,0x798a, 0x7505,0x33df, 0x55f6,0x5ed7
        .hword 0x1f1a,0x7c2a, 0x73b6,0x36ba, 0x5134,0x62f2
        .hword 0x15e2,0x7e1e, 0x7255,0x398d, 0x4c40,0x66d0
        .hword 0x0c8c,0x7f62, 0x70e3,0x3c57, 0x471d,0x6a6e
        .hword 0x0324,0x7ff6, 0x6f5f,0x3f17, 0x41ce,0x6dca
        .hword 0xf9b8,0x7fd9, 0x6dca,0x41ce, 0x3c57,0x70e3
        .hword 0xf055,0x7f0a, 0x6c24,0x447b, 0x36ba,0x73b6
        .hword 0xe707,0x7d8a, 0x6a6e,0x471d, 0x30fc,0x7642
        .hword 0xdddc,0x7b5d, 0x68a7,0x49b4, 0x2b1f,0x7885
        .hword 0xd4e1,0x7885, 0x66d0,0x4c40, 0x2528,0x7a7d
        .hword 0xcc21,0x7505, 0x64e9,0x4ec0, 0x1f1a,0x7c2a
        .hword 0xc3a9,0x70e3, 0x62f2,0x5134, 0x18f9,0x7d8a
        .hword 0xbb85,0x6c24, 0x60ec,0x539b, 0x12c8,0x7e9d
        .hword 0xb3c0,0x66d0, 0x5ed7,0x55f6, 0x0c8c,0x7f62
        .hword 0xac65,0x60ec, 0x5cb4,0x5843, 0x0648,0x7fd9
        .hword 0xa57e,0x5a82, 0x5a82,0x5a82, 0x0000,0x7fff
        .hword 0x9f14,0x539b, 0x5843,0x5cb4, 0xf9b8,0x7fd9
        .hword 0x9930,0x4c40, 0x55f6,0x5ed7, 0xf374,0x7f62
        .hword 0x93dc,0x447b, 0x539b,0x60ec, 0xed38,0x7e9d
        .hword 0x8f1d,0x3c57, 0x5134,0x62f2, 0xe707,0x7d8a
        .hword 0x8afb,0x33df, 0x4ec0,0x64e9, 0xe0e6,0x7c2a
        .hword 0x877b,0x2b1f, 0x4c40,0x66d0, 0xdad8,0x7a7d
        .hword 0x84a3,0x2224, 0x49b4,0x68a7, 0xd4e1,0x7885
        .hword 0x8276,0x18f9, 0x471d,0x6a6e, 0xcf04,0x7642
        .hword 0x80f6,0x0fab, 0x447b,0x6c24, 0xc946,0x73b6
        .hword 0x8027,0x0648, 0x41ce,0x6dca, 0xc3a9,0x70e3
        .hword 0x800a,0xfcdc, 0x3f17,0x6f5f, 0xbe32,0x6dca
        .hword 0x809e,0xf374, 0x3c57,0x70e3, 0xb8e3,0x6a6e
        .hword 0x81e2,0xea1e, 0x398d,0x7255, 0xb3c0,0x66d0
        .hword 0x83d6,0xe0e6, 0x36ba,0x73b6, 0xaecc,0x62f2
        .hword 0x8676,0xd7d9, 0x33df,0x7505, 0xaa0a,0x5ed7
        .hword 0x89be,0xcf04, 0x30fc,0x7642, 0xa57e,0x5a82
        .hword 0x8dab,0xc673, 0x2e11,0x776c, 0xa129,0x55f6
        .hword 0x9236,0xbe32, 0x2b1f,0x7885, 0x9d0e,0x5134
        .hword 0x9759,0xb64c, 0x2827,0x798a, 0x9930,0x4c40
        .hword 0x9d0e,0xaecc, 0x2528,0x7a7d, 0x9592,0x471d
        .hword 0xa34c,0xa7bd, 0x2224,0x7b5d, 0x9236,0x41ce
        .hword 0xaa0a,0xa129, 0x1f1a,0x7c2a, 0x8f1d,0x3c57
        .hword 0xb140,0x9b17, 0x1c0c,0x7ce4, 0x8c4a,0x36ba
        .hword 0xb8e3,0x9592, 0x18f9,0x7d8a, 0x89be,0x30fc
        .hword 0xc0e9,0x90a1, 0x15e2,0x7e1e, 0x877b,0x2b1f
        .hword 0xc946,0x8c4a, 0x12c8,0x7e9d, 0x8583,0x2528
        .hword 0xd1ef,0x8894, 0x0fab,0x7f0a, 0x83d6,0x1f1a
        .hword 0xdad8,0x8583, 0x0c8c,0x7f62, 0x8276,0x18f9
        .hword 0xe3f4,0x831c, 0x096b,0x7fa7, 0x8163,0x12c8
        .hword 0xed38,0x8163, 0x0648,0x7fd9, 0x809e,0x0c8c
        .hword 0xf695,0x8059, 0x0324,0x7ff6, 0x8027,0x0648
        // N=1024 t=2*PI*k/N for k=0,1,2,..,N/4-1
        .hword 0x7fff,0x0000, 0x7fff,0x0000, 0x7fff,0x0000
        .hword 0x7ffa,0x025b, 0x7fff,0x00c9, 0x7ffe,0x0192
        .hword 0x7fea,0x04b6, 0x7ffe,0x0192, 0x7ff6,0x0324
        .hword 0x7fce,0x0711, 0x7ffa,0x025b, 0x7fea,0x04b6
        .hword 0x7fa7,0x096b, 0x7ff6,0x0324, 0x7fd9,0x0648
        .hword 0x7f75,0x0bc4, 0x7ff1,0x03ed, 0x7fc2,0x07d9
        .hword 0x7f38,0x0e1c, 0x7fea,0x04b6, 0x7fa7,0x096b
        .hword 0x7ef0,0x1073, 0x7fe2,0x057f, 0x7f87,0x0afb
        .hword 0x7e9d,0x12c8, 0x7fd9,0x0648, 0x7f62,0x0c8c
        .hword 0x7e3f,0x151c, 0x7fce,0x0711, 0x7f38,0x0e1c
        .hword 0x7dd6,0x176e, 0x7fc2,0x07d9, 0x7f0a,0x0fab
        .hword 0x7d63,0x19be, 0x7fb5,0x08a2, 0x7ed6,0x113a
        .hword 0x7ce4,0x1c0c, 0x7fa7,0x096b, 0x7e9d,0x12c8
        .hword 0x7c5a,0x1e57, 0x7f98,0x0a33, 0x7e60,0x1455
        .hword 0x7bc6,0x209f, 0x7f87,0x0afb, 0x7e1e,0x15e2
        .hword 0x7b27,0x22e5, 0x7f75,0x0bc4, 0x7dd6,0x176e
        .hword 0x7a7d,0x2528, 0x7f62,0x0c8c, 0x7d8a,0x18f9
        .hword 0x79c9,0x2768, 0x7f4e,0x0d54, 0x7d3a,0x1a83
        .hword 0x790a,0x29a4, 0x7f38,0x0e1c, 0x7ce4,0x1c0c
        .hword 0x7840,0x2bdc, 0x7f22,0x0ee4, 0x7c89,0x1d93
        .hword 0x776c,0x2e11, 0x7f0a,0x0fab, 0x7c2a,0x1f1a
        .hword 0x768e,0x3042, 0x7ef0,0x1073, 0x7bc6,0x209f
        .hword 0x75a6,0x326e, 0x7ed6,0x113a, 0x7b5d,0x2224
        .hword 0x74b3,0x3497, 0x7eba,0x1201, 0x7aef,0x23a7
        .hword 0x73b6,0x36ba, 0x7e9d,0x12c8, 0x7a7d,0x2528
        .hword 0x72af,0x38d9, 0x7e7f,0x138f, 0x7a06,0x26a8
        .hword 0x719e,0x3af3, 0x7e60,0x1455, 0x798a,0x2827
        .hword 0x7083,0x3d08, 0x7e3f,0x151c, 0x790a,0x29a4
        .hword 0x6f5f,0x3f17, 0x7e1e,0x15e2, 0x7885,0x2b1f
        .hword 0x6e31,0x4121, 0x7dfb,0x16a8, 0x77fb,0x2c99
        .hword 0x6cf9,0x4326, 0x7dd6,0x176e, 0x776c,0x2e11
        .hword 0x6bb8,0x4524, 0x7db1,0x1833, 0x76d9,0x2f87
        .hword 0x6a6e,0x471d, 0x7d8a,0x18f9, 0x7642,0x30fc
        .hword 0x691a,0x490f, 0x7d63,0x19be, 0x75a6,0x326e
        .hword 0x67bd,0x4afb, 0x7d3a,0x1a83, 0x7505,0x33df
        .hword 0x6657,0x4ce1, 0x7d0f,0x1b47, 0x7460,0x354e
        .hword 0x64e9,0x4ec0, 0x7ce4,0x1c0c, 0x73b6,0x36ba
        .hword 0x6371,0x5098, 0x7cb7,0x1cd0, 0x7308,0x3825
        .hword 0x61f1,0x5269, 0x7c89,0x1d93, 0x7255,0x398d
        .hword 0x6068,0x5433, 0x7c5a,0x1e57, 0x719e,0x3af3
        .hword 0x5ed7,0x55f6, 0x7c2a,0x1f1a, 0x70e3,0x3c57
        .hword 0x5d3e,0x57b1, 0x7bf9,0x1fdd, 0x7023,0x3db8
        .hword 0x5b9d,0x5964, 0x7bc6,0x209f, 0x6f5f,0x3f17
        .hword 0x59f4,0x5b10, 0x7b92,0x2162, 0x6e97,0x4074
        .hword 0x5843,0x5cb4, 0x7b5d,0x2224, 0x6dca,0x41ce
        .hword 0x568a,0x5e50, 0x7b27,0x22e5, 0x6cf9,0x4326
        .hword 0x54ca,0x5fe4, 0x7aef,0x23a7, 0x6c24,0x447b
        .hword 0x5303,0x616f, 0x7ab7,0x2467, 0x6b4b,0x45cd
        .hword 0x5134,0x62f2, 0x7a7d,0x2528, 0x6a6e,0x471d
        .hword 0x4f5e,0x646c, 0x7a42,0x25e8, 0x698c,0x486a
        .hword 0x4d81,0x65de, 0x7a06,0x26a8, 0x68a7,0x49b4
        .hword 0x4b9e,0x6747, 0x79c9,0x2768, 0x67bd,0x4afb
        .hword 0x49b4,0x68a7, 0x798a,0x2827, 0x66d0,0x4c40
        .hword 0x47c4,0x69fd, 0x794a,0x28e5, 0x65de,0x4d81
        .hword 0x45cd,0x6b4b, 0x790a,0x29a4, 0x64e9,0x4ec0
        .hword 0x43d1,0x6c8f, 0x78c8,0x2a62, 0x63ef,0x4ffb
        .hword 0x41ce,0x6dca, 0x7885,0x2b1f, 0x62f2,0x5134
        .hword 0x3fc6,0x6efb, 0x7840,0x2bdc, 0x61f1,0x5269
        .hword 0x3db8,0x7023, 0x77fb,0x2c99, 0x60ec,0x539b
        .hword 0x3ba5,0x7141, 0x77b4,0x2d55, 0x5fe4,0x54ca
        .hword 0x398d,0x7255, 0x776c,0x2e11, 0x5ed7,0x55f6
        .hword 0x3770,0x735f, 0x7723,0x2ecc, 0x5dc8,0x571e
        .hword 0x354e,0x7460, 0x76d9,0x2f87, 0x5cb4,0x5843
        .hword 0x3327,0x7556, 0x768e,0x3042, 0x5b9d,0x5964
        .hword 0x30fc,0x7642, 0x7642,0x30fc, 0x5a82,0x5a82
        .hword 0x2ecc,0x7723, 0x75f4,0x31b5, 0x5964,0x5b9d
        .hword 0x2c99,0x77fb, 0x75a6,0x326e, 0x5843,0x5cb4
        .hword 0x2a62,0x78c8, 0x7556,0x3327, 0x571e,0x5dc8
        .hword 0x2827,0x798a, 0x7505,0x33df, 0x55f6,0x5ed7
        .hword 0x25e8,0x7a42, 0x74b3,0x3497, 0x54ca,0x5fe4
        .hword 0x23a7,0x7aef, 0x7460,0x354e, 0x539b,0x60ec
        .hword 0x2162,0x7b92, 0x740b,0x3604, 0x5269,0x61f1
        .hword 0x1f1a,0x7c2a, 0x73b6,0x36ba, 0x5134,0x62f2
        .hword 0x1cd0,0x7cb7, 0x735f,0x3770, 0x4ffb,0x63ef
        .hword 0x1a83,0x7d3a, 0x7308,0x3825, 0x4ec0,0x64e9
        .hword 0x1833,0x7db1, 0x72af,0x38d9, 0x4d81,0x65de
        .hword 0x15e2,0x7e1e, 0x7255,0x398d, 0x4c40,0x66d0
        .hword 0x138f,0x7e7f, 0x71fa,0x3a40, 0x4afb,0x67bd
        .hword 0x113a,0x7ed6, 0x719e,0x3af3, 0x49b4,0x68a7
        .hword 0x0ee4,0x7f22, 0x7141,0x3ba5, 0x486a,0x698c
        .hword 0x0c8c,0x7f62, 0x70e3,0x3c57, 0x471d,0x6a6e
        .hword 0x0a33,0x7f98, 0x7083,0x3d08, 0x45cd,0x6b4b
        .hword 0x07d9,0x7fc2, 0x7023,0x3db8, 0x447b,0x6c24
        .hword 0x057f,0x7fe2, 0x6fc2,0x3e68, 0x4326,0x6cf9
        .hword 0x0324,0x7ff6, 0x6f5f,0x3f17, 0x41ce,0x6dca
        .hword 0x00c9,0x7fff, 0x6efb,0x3fc6, 0x4074,0x6e97
        .hword 0xfe6e,0x7ffe, 0x6e97,0x4074, 0x3f17,0x6f5f
        .hword 0xfc13,0x7ff1, 0x6e31,0x4121, 0x3db8,0x7023
        .hword 0xf9b8,0x7fd9, 0x6dca,0x41ce, 0x3c57,0x70e3
        .hword 0xf75e,0x7fb5, 0x6d62,0x427a, 0x3af3,0x719e
        .hword 0xf505,0x7f87, 0x6cf9,0x4326, 0x398d,0x7255
        .hword 0xf2ac,0x7f4e, 0x6c8f,0x43d1, 0x3825,0x7308
        .hword 0xf055,0x7f0a, 0x6c24,0x447b, 0x36ba,0x73b6
        .hword 0xedff,0x7eba, 0x6bb8,0x4524, 0x354e,0x7460
        .hword 0xebab,0x7e60, 0x6b4b,0x45cd, 0x33df,0x7505
        .hword 0xe958,0x7dfb, 0x6add,0x4675, 0x326e,0x75a6
        .hword 0xe707,0x7d8a, 0x6a6e,0x471d, 0x30fc,0x7642
        .hword 0xe4b9,0x7d0f, 0x69fd,0x47c4, 0x2f87,0x76d9
        .hword 0xe26d,0x7c89, 0x698c,0x486a, 0x2e11,0x776c
        .hword 0xe023,0x7bf9, 0x691a,0x490f, 0x2c99,0x77fb
        .hword 0xdddc,0x7b5d, 0x68a7,0x49b4, 0x2b1f,0x7885
        .hword 0xdb99,0x7ab7, 0x6832,0x4a58, 0x29a4,0x790a
        .hword 0xd958,0x7a06, 0x67bd,0x4afb, 0x2827,0x798a
        .hword 0xd71b,0x794a, 0x6747,0x4b9e, 0x26a8,0x7a06
        .hword 0xd4e1,0x7885, 0x66d0,0x4c40, 0x2528,0x7a7d
        .hword 0xd2ab,0x77b4, 0x6657,0x4ce1, 0x23a7,0x7aef
        .hword 0xd079,0x76d9, 0x65de,0x4d81, 0x2224,0x7b5d
        .hword 0xce4b,0x75f4, 0x6564,0x4e21, 0x209f,0x7bc6
        .hword 0xcc21,0x7505, 0x64e9,0x4ec0, 0x1f1a,0x7c2a
        .hword 0xc9fc,0x740b, 0x646c,0x4f5e, 0x1d93,0x7c89
        .hword 0xc7db,0x7308, 0x63ef,0x4ffb, 0x1c0c,0x7ce4
        .hword 0xc5c0,0x71fa, 0x6371,0x5098, 0x1a83,0x7d3a
        .hword 0xc3a9,0x70e3, 0x62f2,0x5134, 0x18f9,0x7d8a
        .hword 0xc198,0x6fc2, 0x6272,0x51cf, 0x176e,0x7dd6
        .hword 0xbf8c,0x6e97, 0x61f1,0x5269, 0x15e2,0x7e1e
        .hword 0xbd86,0x6d62, 0x616f,0x5303, 0x1455,0x7e60
        .hword 0xbb85,0x6c24, 0x60ec,0x539b, 0x12c8,0x7e9d
        .hword 0xb98b,0x6add, 0x6068,0x5433, 0x113a,0x7ed6
        .hword 0xb796,0x698c, 0x5fe4,0x54ca, 0x0fab,0x7f0a
        .hword 0xb5a8,0x6832, 0x5f5e,0x5560, 0x0e1c,0x7f38
        .hword 0xb3c0,0x66d0, 0x5ed7,0x55f6, 0x0c8c,0x7f62
        .hword 0xb1df,0x6564, 0x5e50,0x568a, 0x0afb,0x7f87
        .hword 0xb005,0x63ef, 0x5dc8,0x571e, 0x096b,0x7fa7
        .hword 0xae31,0x6272, 0x5d3e,0x57b1, 0x07d9,0x7fc2
        .hword 0xac65,0x60ec, 0x5cb4,0x5843, 0x0648,0x7fd9
        .hword 0xaaa0,0x5f5e, 0x5c29,0x58d4, 0x04b6,0x7fea
        .hword 0xa8e2,0x5dc8, 0x5b9d,0x5964, 0x0324,0x7ff6
        .hword 0xa72c,0x5c29, 0x5b10,0x59f4, 0x0192,0x7ffe
        .hword 0xa57e,0x5a82, 0x5a82,0x5a82, 0x0000,0x7fff
        .hword 0xa3d7,0x58d4, 0x59f4,0x5b10, 0xfe6e,0x7ffe
        .hword 0xa238,0x571e, 0x5964,0x5b9d, 0xfcdc,0x7ff6
        .hword 0xa0a2,0x5560, 0x58d4,0x5c29, 0xfb4a,0x7fea
        .hword 0x9f14,0x539b, 0x5843,0x5cb4, 0xf9b8,0x7fd9
        .hword 0x9d8e,0x51cf, 0x57b1,0x5d3e, 0xf827,0x7fc2
        .hword 0x9c11,0x4ffb, 0x571e,0x5dc8, 0xf695,0x7fa7
        .hword 0x9a9c,0x4e21, 0x568a,0x5e50, 0xf505,0x7f87
        .hword 0x9930,0x4c40, 0x55f6,0x5ed7, 0xf374,0x7f62
        .hword 0x97ce,0x4a58, 0x5560,0x5f5e, 0xf1e4,0x7f38
        .hword 0x9674,0x486a, 0x54ca,0x5fe4, 0xf055,0x7f0a
        .hword 0x9523,0x4675, 0x5433,0x6068, 0xeec6,0x7ed6
        .hword 0x93dc,0x447b, 0x539b,0x60ec, 0xed38,0x7e9d
        .hword 0x929e,0x427a, 0x5303,0x616f, 0xebab,0x7e60
        .hword 0x9169,0x4074, 0x5269,0x61f1, 0xea1e,0x7e1e
        .hword 0x903e,0x3e68, 0x51cf,0x6272, 0xe892,0x7dd6
        .hword 0x8f1d,0x3c57, 0x5134,0x62f2, 0xe707,0x7d8a
        .hword 0x8e06,0x3a40, 0x5098,0x6371, 0xe57d,0x7d3a
        .hword 0x8cf8,0x3825, 0x4ffb,0x63ef, 0xe3f4,0x7ce4
        .hword 0x8bf5,0x3604, 0x4f5e,0x646c, 0xe26d,0x7c89
        .hword 0x8afb,0x33df, 0x4ec0,0x64e9, 0xe0e6,0x7c2a
        .hword 0x8a0c,0x31b5, 0x4e21,0x6564, 0xdf61,0x7bc6
        .hword 0x8927,0x2f87, 0x4d81,0x65de, 0xdddc,0x7b5d
        .hword 0x884c,0x2d55, 0x4ce1,0x6657, 0xdc59,0x7aef
        .hword 0x877b,0x2b1f, 0x4c40,0x66d0, 0xdad8,0x7a7d
        .hword 0x86b6,0x28e5, 0x4b9e,0x6747, 0xd958,0x7a06
        .hword 0x85fa,0x26a8, 0x4afb,0x67bd, 0xd7d9,0x798a
        .hword 0x8549,0x2467, 0x4a58,0x6832, 0xd65c,0x790a
        .hword 0x84a3,0x2224, 0x49b4,0x68a7, 0xd4e1,0x7885
        .hword 0x8407,0x1fdd, 0x490f,0x691a, 0xd367,0x77fb
        .hword 0x8377,0x1d93, 0x486a,0x698c, 0xd1ef,0x776c
        .hword 0x82f1,0x1b47, 0x47c4,0x69fd, 0xd079,0x76d9
        .hword 0x8276,0x18f9, 0x471d,0x6a6e, 0xcf04,0x7642
        .hword 0x8205,0x16a8, 0x4675,0x6add, 0xcd92,0x75a6
        .hword 0x81a0,0x1455, 0x45cd,0x6b4b, 0xcc21,0x7505
        .hword 0x8146,0x1201, 0x4524,0x6bb8, 0xcab2,0x7460
        .hword 0x80f6,0x0fab, 0x447b,0x6c24, 0xc946,0x73b6
        .hword 0x80b2,0x0d54, 0x43d1,0x6c8f, 0xc7db,0x7308
        .hword 0x8079,0x0afb, 0x4326,0x6cf9, 0xc673,0x7255
        .hword 0x804b,0x08a2, 0x427a,0x6d62, 0xc50d,0x719e
        .hword 0x8027,0x0648, 0x41ce,0x6dca, 0xc3a9,0x70e3
        .hword 0x800f,0x03ed, 0x4121,0x6e31, 0xc248,0x7023
        .hword 0x8002,0x0192, 0x4074,0x6e97, 0xc0e9,0x6f5f
        .hword 0x8001,0xff37, 0x3fc6,0x6efb, 0xbf8c,0x6e97
        .hword 0x800a,0xfcdc, 0x3f17,0x6f5f, 0xbe32,0x6dca
        .hword 0x801e,0xfa81, 0x3e68,0x6fc2, 0xbcda,0x6cf9
        .hword 0x803e,0xf827, 0x3db8,0x7023, 0xbb85,0x6c24
        .hword 0x8068,0xf5cd, 0x3d08,0x7083, 0xba33,0x6b4b
        .hword 0x809e,0xf374, 0x3c57,0x70e3, 0xb8e3,0x6a6e
        .hword 0x80de,0xf11c, 0x3ba5,0x7141, 0xb796,0x698c
        .hword 0x812a,0xeec6, 0x3af3,0x719e, 0xb64c,0x68a7
        .hword 0x8181,0xec71, 0x3a40,0x71fa, 0xb505,0x67bd
        .hword 0x81e2,0xea1e, 0x398d,0x7255, 0xb3c0,0x66d0
        .hword 0x824f,0xe7cd, 0x38d9,0x72af, 0xb27f,0x65de
        .hword 0x82c6,0xe57d, 0x3825,0x7308, 0xb140,0x64e9
        .hword 0x8349,0xe330, 0x3770,0x735f, 0xb005,0x63ef
        .hword 0x83d6,0xe0e6, 0x36ba,0x73b6, 0xaecc,0x62f2
        .hword 0x846e,0xde9e, 0x3604,0x740b, 0xad97,0x61f1
        .hword 0x8511,0xdc59, 0x354e,0x7460, 0xac65,0x60ec
        .hword 0x85be,0xda18, 0x3497,0x74b3, 0xab36,0x5fe4
        .hword 0x8676,0xd7d9, 0x33df,0x7505, 0xaa0a,0x5ed7
        .hword 0x8738,0xd59e, 0x3327,0x7556, 0xa8e2,0x5dc8
        .hword 0x8805,0xd367, 0x326e,0x75a6, 0xa7bd,0x5cb4
        .hword 0x88dd,0xd134, 0x31b5,0x75f4, 0xa69c,0x5b9d
        .hword 0x89be,0xcf04, 0x30fc,0x7642, 0xa57e,0x5a82
        .hword 0x8aaa,0xccd9, 0x3042,0x768e, 0xa463,0x5964
        .hword 0x8ba0,0xcab2, 0x2f87,0x76d9, 0xa34c,0x5843
        .hword 0x8ca1,0xc890, 0x2ecc,0x7723, 0xa238,0x571e
        .hword 0x8dab,0xc673, 0x2e11,0x776c, 0xa129,0x55f6
        .hword 0x8ebf,0xc45b, 0x2d55,0x77b4, 0xa01c,0x54ca
        .hword 0x8fdd,0xc248, 0x2c99,0x77fb, 0x9f14,0x539b
        .hword 0x9105,0xc03a, 0x2bdc,0x7840, 0x9e0f,0x5269
        .hword 0x9236,0xbe32, 0x2b1f,0x7885, 0x9d0e,0x5134
        .hword 0x9371,0xbc2f, 0x2a62,0x78c8, 0x9c11,0x4ffb
        .hword 0x94b5,0xba33, 0x29a4,0x790a, 0x9b17,0x4ec0
        .hword 0x9603,0xb83c, 0x28e5,0x794a, 0x9a22,0x4d81
        .hword 0x9759,0xb64c, 0x2827,0x798a, 0x9930,0x4c40
        .hword 0x98b9,0xb462, 0x2768,0x79c9, 0x9843,0x4afb
        .hword 0x9a22,0xb27f, 0x26a8,0x7a06, 0x9759,0x49b4
        .hword 0x9b94,0xb0a2, 0x25e8,0x7a42, 0x9674,0x486a
        .hword 0x9d0e,0xaecc, 0x2528,0x7a7d, 0x9592,0x471d
        .hword 0x9e91,0xacfd, 0x2467,0x7ab7, 0x94b5,0x45cd
        .hword 0xa01c,0xab36, 0x23a7,0x7aef, 0x93dc,0x447b
        .hword 0xa1b0,0xa976, 0x22e5,0x7b27, 0x9307,0x4326
        .hword 0xa34c,0xa7bd, 0x2224,0x7b5d, 0x9236,0x41ce
        .hword 0xa4f0,0xa60c, 0x2162,0x7b92, 0x9169,0x4074
        .hword 0xa69c,0xa463, 0x209f,0x7bc6, 0x90a1,0x3f17
        .hword 0xa84f,0xa2c2, 0x1fdd,0x7bf9, 0x8fdd,0x3db8
        .hword 0xaa0a,0xa129, 0x1f1a,0x7c2a, 0x8f1d,0x3c57
        .hword 0xabcd,0x9f98, 0x1e57,0x7c5a, 0x8e62,0x3af3
        .hword 0xad97,0x9e0f, 0x1d93,0x7c89, 0x8dab,0x398d
        .hword 0xaf68,0x9c8f, 0x1cd0,0x7cb7, 0x8cf8,0x3825
        .hword 0xb140,0x9b17, 0x1c0c,0x7ce4, 0x8c4a,0x36ba
        .hword 0xb31f,0x99a9, 0x1b47,0x7d0f, 0x8ba0,0x354e
        .hword 0xb505,0x9843, 0x1a83,0x7d3a, 0x8afb,0x33df
        .hword 0xb6f1,0x96e6, 0x19be,0x7d63, 0x8a5a,0x326e
        .hword 0xb8e3,0x9592, 0x18f9,0x7d8a, 0x89be,0x30fc
        .hword 0xbadc,0x9448, 0x1833,0x7db1, 0x8927,0x2f87
        .hword 0xbcda,0x9307, 0x176e,0x7dd6, 0x8894,0x2e11
        .hword 0xbedf,0x91cf, 0x16a8,0x7dfb, 0x8805,0x2c99
        .hword 0xc0e9,0x90a1, 0x15e2,0x7e1e, 0x877b,0x2b1f
        .hword 0xc2f8,0x8f7d, 0x151c,0x7e3f, 0x86f6,0x29a4
        .hword 0xc50d,0x8e62, 0x1455,0x7e60, 0x8676,0x2827
        .hword 0xc727,0x8d51, 0x138f,0x7e7f, 0x85fa,0x26a8
        .hword 0xc946,0x8c4a, 0x12c8,0x7e9d, 0x8583,0x2528
        .hword 0xcb69,0x8b4d, 0x1201,0x7eba, 0x8511,0x23a7
        .hword 0xcd92,0x8a5a, 0x113a,0x7ed6, 0x84a3,0x2224
        .hword 0xcfbe,0x8972, 0x1073,0x7ef0, 0x843a,0x209f
        .hword 0xd1ef,0x8894, 0x0fab,0x7f0a, 0x83d6,0x1f1a
        .hword 0xd424,0x87c0, 0x0ee4,0x7f22, 0x8377,0x1d93
        .hword 0xd65c,0x86f6, 0x0e1c,0x7f38, 0x831c,0x1c0c
        .hword 0xd898,0x8637, 0x0d54,0x7f4e, 0x82c6,0x1a83
        .hword 0xdad8,0x8583, 0x0c8c,0x7f62, 0x8276,0x18f9
        .hword 0xdd1b,0x84d9, 0x0bc4,0x7f75, 0x822a,0x176e
        .hword 0xdf61,0x843a, 0x0afb,0x7f87, 0x81e2,0x15e2
        .hword 0xe1a9,0x83a6, 0x0a33,0x7f98, 0x81a0,0x1455
        .hword 0xe3f4,0x831c, 0x096b,0x7fa7, 0x8163,0x12c8
        .hword 0xe642,0x829d, 0x08a2,0x7fb5, 0x812a,0x113a
        .hword 0xe892,0x822a, 0x07d9,0x7fc2, 0x80f6,0x0fab
        .hword 0xeae4,0x81c1, 0x0711,0x7fce, 0x80c8,0x0e1c
        .hword 0xed38,0x8163, 0x0648,0x7fd9, 0x809e,0x0c8c
        .hword 0xef8d,0x8110, 0x057f,0x7fe2, 0x8079,0x0afb
        .hword 0xf1e4,0x80c8, 0x04b6,0x7fea, 0x8059,0x096b
        .hword 0xf43c,0x808b, 0x03ed,0x7ff1, 0x803e,0x07d9
        .hword 0xf695,0x8059, 0x0324,0x7ff6, 0x8027,0x0648
        .hword 0xf8ef,0x8032, 0x025b,0x7ffa, 0x8016,0x04b6
        .hword 0xfb4a,0x8016, 0x0192,0x7ffe, 0x800a,0x0324
        .hword 0xfda5,0x8006, 0x00c9,0x7fff, 0x8002,0x0192
        // N=4096 t=2*PI*k/N for k=0,1,2,..,N/4-1
